package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/count-largest-group/'>统计最大组的数目(Count Largest Group)</a>
 * <p>给你一个整数 n 。请你先求出从 1 到 n 的每个整数 10 进制表示下的数位和（每一位上的数字相加），然后把数位和相等的数字放到同一个组中。</p>
 * <p>请你统计每个组中的数字数目，并返回数字数目并列最多的组有多少个。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：n = 13
 *      输出：4
 *      解释：总共有 9 个组，将 1 到 13 按数位求和后这些组分别是：
 *      [1,10]，[2,11]，[3,12]，[4,13]，[5]，[6]，[7]，[8]，[9]。总共有 4 个组拥有的数字并列最多。
 *
 * 示例 2：
 *      输入：n = 2
 *      输出：2
 *      解释：总共有 2 个大小为 1 的组 [1]，[2]。
 *
 * 示例 3：
 *      输入：n = 15
 *      输出：6
 *
 * 示例 4：
 *      输入：n = 24
 *      输出：5
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>1 <= n <= 10^4</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/12/20 15:16
 */
public class LC1399CountLargestGroup_S {

    static class Solution {
        public int countLargestGroup(int n) {
            // 求每一位的位数上数字之和。并求相同数字之和出现的次数
            int[] cnt = new int[37];
            // 找出数组中的组最大值
            int max = 0;
            for (int i = 1; i <= n; i++) {
                int temp = i;
                int group = 0;
                while (temp != 0) {
                    group += temp % 10;
                    temp /= 10;
                }
                ++cnt[group];
                max = Math.max(max, cnt[group]);
            }
            // 求相同数字之和出现的最多的次数是多少
            int ans = 0;
            for (int num : cnt) {
                if (num == max) {
                    ++ans;
                }
            }
            return ans;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.countLargestGroup(13));
        System.out.println(solution.countLargestGroup(2));
        System.out.println(solution.countLargestGroup(15));
        System.out.println(solution.countLargestGroup(24));
        System.out.println(solution.countLargestGroup(3853));
    }
}
